package com.lfg.leetcode.leetcode0;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class No60getPermutation {

    public static void main(String[] args) {
        String ret = getPermutation(3, 2);
        System.out.println(ret);
    }

    public static String getPermutation(int n, int k) {
        if (n <= 0 || k < 0) {
            return "";
        }
        int size = 1;
        int m = n;
        while (m > 0) {
            size *= m--;
        }
        if (k > size) {
            return "";
        }
        List<Integer> nums = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            nums.add(i);
        }
        k--;
        StringBuilder sb = new StringBuilder();
        for (int i = n; i > 0; ) {
            size = size / i--;
            if (size < 1) {
                size = 1;
            }
            int index = k / size;
            index = getIndex(nums, index);
            sb.append(index);
            k = k % size;
        }
        return sb.toString();
    }

    private static int getIndex(List<Integer> num, int index) {
        if (index < num.size()) {
            return num.remove(index) + 1;
        }
        return num.size();
    }


    public static String getPermutation2(int n, int k) {
        if (n <= 0 || k < 0) {
            return "";
        }
        int size = 1;
        int m = n;
        while (m > 0) {
            size *= m--;
        }
        if (k > size) {
            return "";
        }
        List<String> ret = getList(n, size, k);
        if (k > ret.size()) {
            return "";
        }
        return ret.get(k - 1);
    }

    public static List<String> getList(int n, int size, int index) {
        List<String> ret = new ArrayList<>(size);
        boolean[] values = new boolean[n];
        StringBuilder sb = new StringBuilder(n);
        dp(values, sb, ret, index);
        return ret;
    }

    private static void dp(boolean[] values, StringBuilder sb, List<String> ret, int index) {
        if (sb.length() == values.length) {
            ret.add(sb.toString());
            return;
        }
        for (int i = 0; i < values.length; i++) {
            if (values[i]) {
                continue;
            }
            sb.append(i + 1);
            values[i] = true;
            dp(values, sb, ret, index);
            if (ret.size() >= index) {
                return;
            }
            values[i] = false;
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

